package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;
import cn.pugle.oj.catalog.TwoProblem;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * faster than 5.02%
 * <p>
 * 滑动窗口
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC76_2 implements TwoProblem, Greedy {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        Map<Integer, List<Integer>> targetChars = new HashMap<>();
        Map<Integer, Integer> targetNums = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            targetChars.put((int) t.charAt(i), new LinkedList<>());
            targetNums.compute((int) t.charAt(i), (key, oldValue) -> oldValue == null ? 1 : oldValue + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (targetChars.containsKey((int) s.charAt(i))) {
                targetChars.get((int) s.charAt(i)).add(i);
            }
        }
        int leftMax = Integer.MAX_VALUE, rightMax = Integer.MIN_VALUE;
        //初始窗口
        for (Integer key : targetNums.keySet()) {
            Integer targetNum = targetNums.get((int) key);
            List<Integer> list = targetChars.get((int) key);
            if (targetNum > list.size()) return "";
            leftMax = Math.min(leftMax, list.get(0));
            rightMax = Math.max(rightMax, list.get(targetNum - 1));
        }

        int minSub = rightMax - leftMax + 1;
        String result = s.substring(leftMax, rightMax + 1);
        //开始滑动
        while (leftMax < rightMax) {
            if (rightMax - leftMax + 1 < minSub) {
                minSub = rightMax - leftMax + 1;
                result = s.substring(leftMax, rightMax + 1);
            }
            int cur = (int) s.charAt(leftMax);
            if (targetChars.containsKey(cur)) {
                List<Integer> list = targetChars.get(cur);
                Integer targetNum = targetNums.get(cur);
                if (targetNum == list.size()) {
                    break;
                } else {
                    list.remove(0);
                    rightMax = Math.max(rightMax, list.get(targetNum - 1));
                    leftMax++;
                }
            } else {
                leftMax++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(new LC76().minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(new LC76().minWindow("AZZZZZAxBxCZZZZZCZ", "ABC"));
        System.out.println(new LC76_1().minWindow("a", "aa"));
        System.out.println(new LC76_1().minWindow("a", "ab"));
        System.out.println(new LC76_2().minWindow("cabwefgewcwaefgcf", "cae"));
        //aefgc
        //cabwe
        //cwae
    }
}
